<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            完全背包爬楼梯
            题目描述: 
                给你一组硬币数，表示不同面额的硬币；以及一个整数amount，表示总金额；
                计算并返回可以凑成总金额所需的最少硬币个数
            示例 1：

            输入：coins = [1, 2, 5], amount = 11
            输出：3 
            解释：11 = 5 + 5 + 1

            示例 2：

            输入：coins = [2], amount = 3
            输出：-1
            示例 3：

            输入：coins = [1], amount = 0
            输出：0
        */


        /*
        */

        /* 
            这里的时间复杂度不确定行不行
            时间复杂度：O(n * m)
            空间复杂度：O(n)
        */
        var coinChange = function(coins, amount) {
            // 提前对硬币进行排序操作更好
            let len = coins.length
            let min = Infinity;
            function trackback(res, index, count) {
                // 剪枝操作
                if (count >= min) return
                if (res < 0) return
                if (res === 0) {
                    min = Math.min(min, count)
                    return
                }
                if (index < 0) return
                for (let i = Math.floor(amount / coins[index - 1]); i >= 0; i--) {
                    // 倒着去遍历硬币，count + 1 而不是count++
                    let remain = res - i * coins[index - 1]
                    trackback(remain, index - 1, count + 1)
                }
            }
            trackback(amount, len, 0)
            return min === Infinity ? -1 : min
        };
        console.log(coinChange([1, 2, 5], 11));
        // console.time('100');
        // console.log(coinChange([1, 1, 1], 1111));
        // console.timeEnd('100');
        // console.log(coinChange([2], 3));
        // console.log(coinChange([1], 0));
    </script>
</body>

</html>